{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "measure clock error between hosts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Agenda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Timekeeping, how NTP works\n",
    "- Roundtrip, measure clock error between hosts\n",
    "- UDP vs. TCP from programmingprospective"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The science of time keeping*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Time is the most accurate quantity we measure in our daily life\n",
    "  - 2014-10-31 12:34:56 PDT ~ 10 significant figures (86400x365x70)\n",
    "  - Length, weight, even money, much lower precision, usually 3~4 digits\n",
    "\n",
    "- A clock =An oscillator + a counter\n",
    "\t- Current time = count / frequency + offset\n",
    "\t- The quality(accuracy and stability) of the oscillator dominates\n",
    "\t- Quartz crystal oscillators are commonly used"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 时间的精度\n",
    "- 时钟: 振荡器+计数器, 主要改进振动器\n",
    "  - http://www.allanstime.com/Publications/DWA/Science_Timekeeping/\n",
    "  - 当前时间 = 计数值(精确)/频率 + 起止时间\n",
    "  - 晶振, 一般以14.318MHz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Crystal oscillators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "14.318 MHz = 4 x 3.579545MHz (NTSC subcarrier*)\n",
    "- IBM PC 5150 runs i8088 at 4.77MHz, 4.77 = 14.318/3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Comparison** (XO = crystal oscillator)\n",
    "\n",
    "| Oscillator      | Accuracy(准确度)     | Drift per day (ms) | Cost ($) |                  |\n",
    "| --------------- | ------------ | ------------------ | -------- | ---------------- |\n",
    "| Clock XO        | 10 ~ 100 ppm | 864                | 0.x      |                  |\n",
    "| TCXO            | 1ppm         | 86.4               | x        |                  |\n",
    "| OCXO            | 0.1ppm       | 8.64               | xx       |                  |\n",
    "| Rb atomic clock | 1ppb         | 0.0864             | xxx      | FE-5680A         |\n",
    "| Cs atomic clock | 10^-12       | <86.4ns            | xxxx     | HP Agilent 5071A |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- http://en.wikipedia.org/wiki/Colorburst#Crystals\n",
    "- http://en.wikipedia.org/wiki/Crystal_oven#Comparison_with_other_frequency_standards"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Accuracy, precision, and stability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Frequency changes\n",
    "- Temperature\n",
    "- Aging\n",
    "\n",
    "What do we measure?\n",
    "- Timestamp\n",
    "- Time interval\n",
    "\n",
    "https://www.ieee.li/pdf/viewgraphs/precision_frequency_generation.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 准确度与精度的关系\n",
    "\n",
    "![3.1](./images/3.1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 晶体振荡器频率会随着温度, 时间变化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 测当前时间(时间点): 相当于`T*`, 同类型只能相减, 不能相加; `T*`可以加减`int`; `(T1+T2)/2 = T1 + (T2-T1)/2`\n",
    "- 测时间间隔: 相当于`int`, 同类型既能相加, 又能相减;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 如何判断时钟是否准确, 与和一个更准的时钟对比"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How to keep pendulum clock accurate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$T = 2\\pi\\sqrt{L/g}$\n",
    "\n",
    "- Not only sync with broadcast-ing everyday\n",
    "- But also adjust the length of pendulum accordingly"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| Calculus   | Driving a car | Timekeeping |\n",
    "| ---------- | ------------- | ----------- |\n",
    "|    | distance(距离) | time(时间)   |\n",
    "| derivative  | velocity(速度) | frequency(频率)   |\n",
    "| 2nd order derivative | acceleration(加速度)  | jitter(频率的变化率) |\n",
    "\n",
    "- It's a feedback system, basically\n",
    "  - Input is the difference to reference standard\n",
    "  - Output is to adjust theoffset and frequency, everyday"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 钟摆的`L`可能会变: 温度, 湿度, 热胀冷缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Timekeeping in Linux Kernel"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- High-resolution kernel timers since 2.6.16\n",
    "- Multiple clock sources, tsc iscommonly chosen\n",
    "- Resolution: 1/frequency\n",
    "  - 1us (gettimeofday) or 1ns (clock_gettime)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 多核CPU时代, tsc存在问题, CPU频率也影响tsc; \n",
    "- 新的CPU的tsc跟CPU频率无关了, 多个CPU之间是同步的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- [Hrtimersand Beyond: Transforming the Linux Time Subsystems (2006)](https://www.kernel.org/doc/ols/2006/ols2006v1-pages-333-346.pdf)\n",
    "- [Timekeeping in VMware Virtual Machines](https://www.vmware.com/docs/vmware_timekeeping)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> NTP（Network Time Protocol）建议使用FreeBSD"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Network Time Synchronization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Daytime (RFC 867), Time (RFC 868)\n",
    "- NTPv3 (RPC 1305), NTPv4 (RFC 5905)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![3.2](./images/3.2.png)\n",
    "\n",
    "- Daytime: 字符串, 精确到秒; Time:四个字节二进制消息, 精确到秒; 精确到秒, 会有误差; 不知道网络传输时间(网络延迟)\n",
    "- NTP解决不能以秒为单位, 是大概0.25ns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How NTP works"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![3.3](./images/3.3.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Measure clock error \n",
    "  - SCM_TIMESTAMP\n",
    "  - $\\frac{(T_4 + T_1) - (T_2 + T_3)}{2}$\n",
    "- Adjust offset and frequency, continuously\n",
    "- Avoid time jump\n",
    "- Deal with leap seconds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- NTP基于UDP, 收发消息, 消息带有时间戳(T1-客户端发出, T2-服务端收到, T3-服务端发出)\n",
    "- 本机时钟运行频率与服务器时钟运行频率对比, 进行调整; NTP不可能做到与服务器差值为0, 阈值大约128ms\n",
    "- 避免时间跳变, 频率跳变; 尽量保证\"导数连续\", 变化缓慢\n",
    "- 处理闰秒\n",
    "- NTP的负载均衡"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# NTP kernel clock discipline*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://www.eecis.udel.edu/~mills/precision.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![3.4](./images/3.4.png)\n",
    "\n",
    "- Type II, adaptive-parameter, hybrid phase/frequency-lock loop disciplinesvariable frequency oscillator (VFO) phase and frequency\n",
    "- NTP daemon computes phase error ($V_d = \\theta_r - \\theta_o$) between sourceand VFO, then grooms samples to produce time update ($V_s$)\n",
    "- Loop filter computes phase x and frequency y corrections and provides new adjustments ($V_c$) at 1-s intervals\n",
    "- VFO frequency is adjusted at each hardware tick interrupt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 基本听不懂了....\n",
    "\n",
    "\n",
    "1. NTP的算法核心与锁相环介绍 11:13\n",
    "- 算法来源: 基于Mills教授提出的Type II自适应参数混合锁相环算法，详细资料见其精确定时主页\n",
    "- 核心机制: 采用电压控制频率振荡器(VFO)的相位/频率锁定环路，通过相位检测器和环路滤波器实现时钟同步\n",
    "\n",
    "\n",
    "2. NTP的时间差值计算与滤波过程 11:28\n",
    "- 相位检测: NTP守护进程计算源时钟与VFO的相位差$V_d = \\theta_r - \\theta_0$\n",
    "- 信号处理: 差值经过低通滤波和环路滤波双重处理，生成时间更新信号$V_s$\n",
    "- 调整周期: 环路滤波器每秒计算一次相位x和频率y的修正值\n",
    "\n",
    "3. NTP的控制信号生成与VFO调整 11:42\n",
    "- 控制信号: 生成调整信号$V_c$控制VFO，在硬件时钟中断时调整振荡器频率\n",
    "- 双重调节: 同时调整时间频率(f)和相位偏移(offset)，通过count×频率+offset实现精确时间设置\n",
    "\n",
    "4. NTP在内核与守护进程中的实现 12:29\n",
    "- 架构设计: 分为内核态(两个系统调用)和用户态(ntpd守护进程)两部分实现\n",
    "- 时间获取: 守护进程收到时间t2，发送时间t3，但存在内核处理延迟(约微秒级)\n",
    "\n",
    "5. NTP的时间戳获取与误差分析 12:46\n",
    "- 误差来源: 网卡收包到进程唤醒存在延迟，发送时间只能记录用户态时间\n",
    "- 根本限制: 用户态无法直接观测硬件信号状态，必须依赖外部设备进行精确测量\n",
    "- 解决方案: 高精度场景需使用实时操作系统或将NTP直接集成到网卡驱动"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Why do we need to know clock error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Verify NTP works\n",
    "- Measure latency in messaging system\n",
    "  - Timestamps from two clocksare not comparable unless you know their offset (ie. clock error)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 确认NTP是否在工作; 相关命令行: `ntptime`, `ntpq`; \n",
    "- S1<->N1, S2<->N2, 无法确认S1, S2差值, 此时需要测试S1, S2延时; \n",
    "- 同一台机器上的请求响应协议不需要测试延时; \n",
    "- *股票交易所→市场数据(MD)→指标引擎(ENG)→客户连接服务(CC)→交易软件: \n",
    "  - 客户接入你的引擎, 并不能直接接入MD; \n",
    "  - 测量交易所到系统, 系统到客户之间的延时: 需要第三个程序知道MD, CC之间时间误差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Roundtrip protocol and code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![3.5](./images/3.5.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- UDP, two threads\n",
    "  - [recipes/blob/master/tpc/bin/roundtrip_udp.cc](https://github.com/chenshuo/recipes/blob/master/tpc/bin/roundtrip_udp.cc)\n",
    "- UDP with muduo, single thread\n",
    "  - [muduo/examples/roundtrip/roundtrip_udp.cc](https://github.com/Anita-Mul/muduo-chenshuo/blob/master/examples/roundtrip/roundtrip_udp.cc)\n",
    "- TCP with muduo\n",
    "  - [muduo/examples/roundtrip/roundtrip.cc](https://github.com/Anita-Mul/muduo-chenshuo/blob/master/examples/roundtrip/roundtrip.cc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- UDP, two threads: UDP不可靠, 不能发送一个, 等待另外一个, 发送(接受)可能丢失"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "vscode": {
     "languageId": "plaintext"
    }
   },
   "source": [
    "# [roundtrip_udp.cc](https://github.com/chenshuo/recipes/blob/master/tpc/bin/roundtrip_udp.cc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include \"InetAddress.h\"\n",
    "#include \"Socket.h\"\n",
    "\n",
    "#include <thread>\n",
    "\n",
    "#include <stdio.h>\n",
    "#include <string.h>\n",
    "#include <sys/time.h>\n",
    "#include <unistd.h>\n",
    "\n",
    "const int g_port = 3123;\n",
    "\n",
    "struct Message\n",
    "{\n",
    "  int64_t request; // T1\n",
    "  int64_t response; // T2\n",
    "} __attribute__ ((__packed__));\n",
    "\n",
    "static_assert(sizeof(Message) == 16, \"Message size should be 16 bytes\");\n",
    "\n",
    "// 当前时间\n",
    "int64_t now()\n",
    "{\n",
    "  struct timeval tv = { 0, 0 };\n",
    "  gettimeofday(&tv, NULL);\n",
    "  return tv.tv_sec * int64_t(1000000) + tv.tv_usec;\n",
    "}\n",
    "\n",
    "// 服务端\n",
    "// 一个UDP的socket可以服务多个客户端\n",
    "void runServer(bool ipv6)\n",
    "{\n",
    "  Socket sock(Socket::createUDP(ipv6 ? AF_INET6 : AF_INET)); // 创建UDP socket\n",
    "  sock.bindOrDie(InetAddress(g_port, ipv6)); // 绑定端口\n",
    "\n",
    "  while (true)\n",
    "  {\n",
    "    Message message = { 0, 0 };\n",
    "\n",
    "    struct sockaddr_storage peerAddr;\n",
    "    bzero(&peerAddr, sizeof peerAddr);\n",
    "    socklen_t addrLen = sizeof peerAddr;\n",
    "    struct sockaddr* addr = reinterpret_cast<struct sockaddr*>(&peerAddr);\n",
    "\n",
    "    // 读取消息\n",
    "    ssize_t nr = ::recvfrom(sock.fd(), &message, sizeof message, 0, addr, &addrLen);\n",
    "    if (nr == sizeof message)\n",
    "    {\n",
    "      message.response = now(); // 获取当期时间\n",
    "      // 发回客户端\n",
    "      ssize_t nw = ::sendto(sock.fd(), &message, sizeof message, 0, addr, addrLen);\n",
    "      if (nw < 0)\n",
    "      {\n",
    "        perror(\"send Message\");\n",
    "      }\n",
    "      else if (nw != sizeof message)\n",
    "      {\n",
    "        printf(\"sent message of %zd bytes, expect %zd bytes.\\n\", nw, sizeof message);\n",
    "      }\n",
    "    }\n",
    "    else if (nr < 0)\n",
    "    {\n",
    "      perror(\"recv Message\");\n",
    "    }\n",
    "    else\n",
    "    {\n",
    "      printf(\"received message of %zd bytes, expect %zd bytes.\\n\", nr, sizeof message);\n",
    "    }\n",
    "  }\n",
    "}\n",
    "\n",
    "// 客户端 \n",
    "// 比服务端复杂些, 要发消息后, 再接收;\n",
    "// 可以像服务端(口误?)那样写一个循环吗? 先sendto, 然后recvfrom. 在UDP下程序可能会永远阻塞下去, sendto后可能会丢包, recvfrom也可能丢包\n",
    "void runClient(const char* server_hostname)\n",
    "{\n",
    "  InetAddress serverAddr;\n",
    "  if (!InetAddress::resolve(server_hostname, g_port, &serverAddr))\n",
    "  {\n",
    "    printf(\"Unable to resolve %s\\n\", server_hostname);\n",
    "    return;\n",
    "  }\n",
    "\n",
    "  Socket sock(Socket::createUDP(serverAddr.family()));\n",
    "\n",
    "  if (sock.connect(serverAddr) != 0) // 连接服务器地址\n",
    "  {\n",
    "    perror(\"connect to server\");\n",
    "    return;\n",
    "  }\n",
    "\n",
    "  // 启动一个线程\n",
    "  std::thread thr([&sock] () {\n",
    "    while (true)\n",
    "    {\n",
    "      Message message = { 0, 0 };\n",
    "      message.request = now();\n",
    "      int nw = sock.send(&message, sizeof message);\n",
    "      if (nw < 0)\n",
    "      {\n",
    "        perror(\"send Message\");\n",
    "      }\n",
    "      else if (nw != sizeof message)\n",
    "      {\n",
    "        printf(\"sent message of %d bytes, expect %zd bytes.\\n\", nw, sizeof message);\n",
    "      }\n",
    "\n",
    "      ::usleep(200*1000); // 200us, 1s发5个\n",
    "    }\n",
    "  });\n",
    "\n",
    "\n",
    "  // 主线程接收\n",
    "  while (true)\n",
    "  {\n",
    "    Message message = { 0, 0 };\n",
    "    int nr = sock.recv(&message, sizeof message);\n",
    "    if (nr == sizeof message)\n",
    "    {\n",
    "      int64_t back = now();\n",
    "      int64_t mine = (back + message.request) / 2;\n",
    "      printf(\"now %jd, round trip time %jd us, clock error %jd us\\n\",\n",
    "             back, back - message.request, message.response - mine);\n",
    "    }\n",
    "    else if (nr < 0)\n",
    "    {\n",
    "      perror(\"recv Message\");\n",
    "    }\n",
    "    else\n",
    "    {\n",
    "      printf(\"received message of %d bytes, expect %zd bytes.\\n\", nr, sizeof message);\n",
    "    }\n",
    "  }\n",
    "}\n",
    "\n",
    "int main(int argc, const char* argv[])\n",
    "{\n",
    "  if (argc < 2)\n",
    "  {\n",
    "    printf(\"Usage:\\nServer: %s -s [-6]\\nClient: %s server_hostname\\n\", argv[0], argv[0]);\n",
    "    return 0;\n",
    "  }\n",
    "\n",
    "  if (strcmp(argv[1], \"-s\") == 0) // 运行服务端\n",
    "  {\n",
    "    bool ipv6 = argc > 2 ? strcmp(argv[2], \"-6\") == 0 : false;\n",
    "    runServer(ipv6);\n",
    "  }\n",
    "  else\n",
    "  {\n",
    "    runClient(argv[1]);\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 测试"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- atom\n",
    "```shell\n",
    "ntpq -pn\n",
    "./roundtrip_udp -s\n",
    "```\n",
    "\n",
    "- e6400\n",
    "```shell\n",
    "./roundtrip_udp atom\n",
    "```\n",
    "```shell\n",
    "sudo service ntp start\n",
    "./roundtrip_udp atom\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 两台机器之间控制在5ms内, 否则可能是否是硬件不可靠"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- atom\n",
    "```shell\n",
    "./roundtrip_udp -s\n",
    "```\n",
    "\n",
    "- atom\n",
    "```shell\n",
    "./roundtrip_udp localhost\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test configurations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Sanity checks\n",
    "  - Same host, clock error should be close to zero\n",
    "  - Two hosts, clock error should besymmetrical\n",
    "- No NTP, free running\n",
    "- One has NTP enabled, the other free runs\n",
    "- Both has NTP enabled, but syncto different NTP servers\n",
    "- Both has NTP enabled, one serve as the NTP server to the other"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 冒烟测试\n",
    "  - 同一台机器接近0\n",
    "  - 两台机器差值是对称的, 即A Server与B Server差值是正, 反过来应是负; 可以用50个数据,算下平均数\n",
    "- 两台机器都没有NTP: 可能线性变化\n",
    "- 一台机器有NTP, 一台机器无NTP: 大概二次曲线\n",
    "- 两台机器都有NTP, 但是同步到不同的NTP服务器上\n",
    "- 两台机器都有NTP, 但是同步到相同的第三台NTP服务器上\n",
    "- 两台机器都有NTP, 其中一台作为另外一台的NTP服务器\n",
    "\n",
    "> NTP服务器一般购买; 实际部署不只一台, 一般4台, 2台GPS, 2台原子钟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# UDP vs. TCP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "UDP: connection-less, unreliable, datagram protocol\n",
    "- UDP = IP + port (+ weak checksum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TCP: connection-oriented, reliable, byte-stream protocol"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When in doubt, use TCP\n",
    "- http://www.zhihu.com/question/20060141/answer/26735814\n",
    "\n",
    "> UDP 的使用范围很窄，而且编程比 TCP 难多了：\n",
    "> \n",
    "> 你真的很在乎延迟，不能忍受重传，那么就用UDP，例如 NTP 协议。重传NTP消息纯属添乱。\n",
    "> 你真的不在乎可靠性，丢一些包也不需要重传，那么就可以用 UDP。例子我想不出来。有人说音频或视频流可以用UDP，不过据我看来各大视频网站都用HTTP协议，而> HTTP是基于TCP的。\n",
    "> 你需要NAT穿透，那么不得不用UDP。\n",
    "> 其他情况，一旦程序要自己做重传，你都是在用UDP模拟出蹩脚的TCP，还不如直接用TCP呢。\n",
    "> 总之：使用 UDP 需要有强大到不容置疑的理由，when in doubt, use TCP.\n",
    "> \n",
    "> 一些协议，出于历史原因，受当时技术和网络条件限制，选择了基于UDP实现，其选择的理由现在很可能已经不再成立了。因此“xxx协议用UDP”不是你现在写网络应用程序也该用UDP的理由，除非你本身就是在实现xxx协议。\n",
    "> \n",
    "> 另外，那些说TCP比UDP慢、效率低的，你拿UDP写个程序，把千兆网带宽打满（TCP等价的代码只有两行：客户端 `while (true) { send(...); }`, 服务端 `while (true) { recv(...); }`。），且不说你的程序会有多复杂，先看看goodput到底是不是比TCP大、CPU使用率是不是比TCP低嘛。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 2018年HTTP3.0-QUIC, 基于UDP的可靠传输协议, 基本也是重新实现了TCP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Concurrent model: how to manage multiple concurrent clients?\n",
    "- TCP: one socket fd for each client, not thread safe\n",
    "- UDP: usually share one fd for all clients, thread safe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- TCP: 线程不安全, 即两个线程不要同时读一个`fd`, 可能一个线程读取部分字节流\n",
    "- UDP: 线程安全, 数据报文协议, 自动维护边界; 编程难度大于TCP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# UTC, TAI, Leap Seconds, Unix Time "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What’s wrong with leap seconds?\n",
    "- It’s added on June 30 00:00:00Z or Dec 31 00:00:00Z, regardless of weekdays and time zones\n",
    "  - Not all peers are synced, you may receive a message from the future\n",
    "- Clock stops during theleap second, but every time you call `gettimeofday()`, kernel suppose to fake you an increasing time\n",
    "  - Poorly tested in user code, kernels, NTPclients, even NTP servers\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- UTC:原子时, GMT:天文时; UTC = TAI + Leap Seconds; Unix Time是个整数, t/86400 = 天数计算, t % 86400 = 日内秒数, 没法表示闰秒; t是负数时, 取模向0取整而不是向负无穷取整, 负数时间需加86400转为正数后计算，再调整日期\n",
    "- 闰秒的设计失误: \n",
    "  - 固定添加时间：每年6月30日或12月31日23:59:59Z; 未考虑时区差异（如北京时间8:00，东京时间9:00）,可能影响金融市场（订单时间校验异常）\n",
    "  - Unix Time无法表示闰秒（时钟在闰秒期间停止）; 内核通过微秒递增模拟时间连续性（`gettimeofday()`返回虚假递增时间）, 难以测试, 结果造成2012年6月30日闰秒导致多台服务器死循环"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Google blog: *[Time, technology and leaping seconds](https://googleblog.blogspot.com/2011/09/time-technology-and-leaping-seconds.html)*, $lie(t) = \\frac{1}{2} - \\frac{1}{2}\\cos\\frac{\\pi t}{w}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 将1秒跳变分散到时间窗口`w`内, 采用平滑函数$lie(t)$\n",
    "- 时间连续性：函数值从0平滑过渡到1; 频率连续性：一阶导数（变化率）连续; 避免阶跃响应：三角函数无限可导\n",
    "- 窗口`w`长度未公开, 实际应用效果：2011年提出，2014年验证可行"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Relativity of simultaneity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "According to the special theory of relativity, it is impossible to say in an absolute sense that two distinct eventsoccur at the same time if those events are separated in space. It depends on the observer's reference frame."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 空间分离的事件无法绝对判定同时性; 依赖观察者参考系（本地时钟）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Distributed system is relativistic\n",
    "- [Time, Clocks and the Ordering of Events in a Distributed System by Leslie Lamport](https://lamport.azurewebsites.net/pubs/time-clocks.pdf)\n",
    "- [Rethinking Time in Distributed Systems by Paul Borrill](https://web.stanford.edu/class/ee380/Abstracts/091111-RethinkingTime.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Lamport 1978年论文论证分布式系统的相对性\n",
    "- 讲座PPT\n",
    "- 美国东岸与西岸的交易所, 网络延迟：东西海岸约50ms, 同时性不存在的, 事件顺序依赖观察者位置（无因果关系时）\n",
    "- 主板上两个CPU: 电信号传播速度, $2×10^8 m/s$, 3GHz CPU周期内传播距离 = $\\frac{2×10^8}{3×10^9} = 0.066m = 6.6cm$, 典型CPU间距：10-20cm（超过1个时钟周期）; 并发问题: INC指令执行完成顺序无法绝对判定, 内存一致性协议需额外处理因果关系, 无共享内存操作时完全无法确定顺序"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
